package previous.Test_0308;

import java.util.*;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
public class Solution {
    //字符串解码(没写对，需要更改)
    public String decodeString(String s) {
           char[] c=s.toCharArray();
        Stack<Integer> num=new Stack<>();
        Stack<String> strings=new Stack<>();
        strings.push("");
        for (int i = 0; i <c.length ; i++) {
            if(c[i]>='0' && c[i]<='9') {
                StringBuilder stringBuilder1=new StringBuilder();
                while (i< c.length && c[i]>='0' && c[i]<='9'){
                    stringBuilder1.append(c[i]);
                    i++;
                }
                num.push(Integer.parseInt(stringBuilder1.toString()));
            }
            else if(c[i]=='['){
                i++;
                StringBuilder stringBuilder=new StringBuilder();
                while (i< c.length && c[i]>='a' && c[i]<='z'){
                    stringBuilder.append(c[i]);
                    i++;
                }
                strings.push(stringBuilder.toString());
            }else if(c[i]==']'){
                i++;
                StringBuilder stringBuilder2=new StringBuilder();
                for (int j = 0; j < num.pop(); j++) {
                   stringBuilder2=stringBuilder2.append(strings.peek());
                }
                strings.pop();
                strings.push(strings.pop()+stringBuilder2);
            }else {
                StringBuilder stringBuilder=new StringBuilder();
                while (i< c.length && c[i]>='a' && c[i]<='z'){
                    stringBuilder.append(c[i]);
                    i++;
                }
                strings.push(stringBuilder.toString());
            }
        }
        return strings.toString();
    }
    //验证栈序列
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack=new Stack<>();
        int k=0;
        for (int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while(!stack.isEmpty() && stack.peek()==popped[k]){
                stack.pop();
                k++;
            }
        }
        return stack.isEmpty() && k==popped.length;
    }
    //N叉树的层序遍历
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret=new ArrayList<>();
          if(root==null) return ret;
        Queue<Node> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            //统计本层节点信息
            List<Integer> l=new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Node t=queue.poll();
                l.add(t.val);
                for (Node c:t.children) {
                    if(t.children!=null) queue.add(c);
                }
            }
            ret.add(l);
        }
        return ret;
    }
    //二叉树的锯齿形层遍历
    //奇数正序，偶数翻转
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
           List<List<Integer>> ret=new ArrayList<>();
           if(root==null) return ret;
           Queue<TreeNode> queue=new LinkedList<>();
           queue.add(root);
           int level=1;
           while(!queue.isEmpty()){
               int s=queue.size();
               List<Integer> l=new ArrayList<>();
               for (int i = 0; i < s; i++) {
                       TreeNode t=queue.poll();
                       l.add(t.val);
                       if(t.left!=null) queue.add(t.left);
                       if(t.right!=null)  queue.add(t.right);
                   }
                   if(level%2==0){
                       Collections.reverse(l);
                   }
                   ret.add(l);
                   level++;
               }
        return ret;
           }

    }

